package 链表.单链表;

/**
 * 基于int单链表-火车
 * 真正被用户使用的 火车类-单链表对象
 */
public class Single_Linked_List {

    // Node head 这步只是在堆区中开辟了一块小空间，
    //用来保存 Node对象的地址，而head本身并不是对象
    //在这里相当于成员变量，因为对象都是需要 new出来的
    private Node head;//单链表的头
    private int size;//记录有效个数

    //尾插add
    public void add_Last(int val){
//        //这里new一个Node对象出来
//        Node newNode = new Node();
//        //把val值保存在这个车厢里
//        newNode.val = val;
//        if(head == null){
//            //说明此事head没有任何对象(车厢),是第一次
//            head = newNode;
//        }else{
//            //否则说明heda至少已经有一个车厢了，我们需要连接车厢
//            Node num = head;
//            while(num.next != null){
//                //找到最后一节车厢
//               num = num.next;
//            }
//            num.next = newNode;
//        }
//        size++;
        add(val, 1);
    }//尾插add

    //头插add
    public void add_First(int val){
//        //这里new一个Node对象出来
//        Node newNode = new Node();
//        //把val值保存在这个车厢里
//        newNode.val = val;
//        if(head == null){
//            //说明此事head没有任何对象(车厢),是第一次
//            head = newNode;
//        }else{
//            //否则说明heda至少已经有一个车厢了，我们需要连接车厢
//            Node num = head;
//            newNode.next = num;
//            head = newNode;
//
//        }
//        size++;
        add(val, 0);
    } //头插add

    //add添加数
    /**
     * // 当 t == 0时是 头插
     * // 当 t == 1时是 尾插
     */
    private void add(int val, int t){
        //这里new一个Node对象出来
        Node newNode = new Node();
        //把val值保存在这个车厢里
        newNode.val = val;
        if(head == null){
            //说明此事head没有任何对象(车厢),是第一次
            head = newNode;
        }else{
            //否则说明heda至少已经有一个车厢了，我们需要连接车厢
            Node num = head;
            if(t == 1){
                while(num.next != null){
                    //找到最后一节车厢
                    num = num.next;
                }
                num.next = newNode;
            }

            if(t == 0){
                newNode.next = num;
                head = newNode;
            }
        }
        size++;
    } //add添加数

    // 任意位置插入,输入的为 索引位置
    public boolean addIndex(int index,int val){
        if(index < 0 || index > size){
            System.out.println("插入位置错误，请重新输入");
            return false;
        }
        if(index == 0){
            add(val, 0);
        }else if(index == size){
            add(val, 1);
        }else{
            //这种情况保证是插在两个 节点之中
            Node newNode = new Node();
            newNode.val = val;
            Node p1 = head;//保存插入的数之前的节点地址
            Node p2 = head;//保存插入位置后面的节点地址

            while(--index > 0){
                //走到要插入的数之前的节点
                p1 = p1.next;
            }
            p2 = p1.next;//保存插入位置后面的节点地址
            p1.next = newNode;//等于新节点
            newNode.next = p2;//新节点的next等于后面节点的位置
            size++;
        }
        return true;
    }// 任意位置插入,输入的为 索引位置


    //打印整个链表--完善toString的功能
    public String toString(){
        String rep = "";

        Node X = head;
        while(X != null){
            rep += X.val;
            rep += " -> ";
            X = X.next;
        }
        rep += "NULL";
        return rep;
    } //打印整个链表--完善toString的功能

    //查找
    //1. 查找是否存在val的值，存在则返回true，否则返回false
    public boolean search1(int val){

        Node x = head;

        while(x != null){

            if(x.val == val)break;

            x = x.next;
            }
        if(x != null)return true;
        else return false;
    }//1. 查找是否存在val的值，存在则返回true，否则返回false

    //2. 查找 index 位置处的 信息,存在则打印其val值
    public void search2(int index){
        //判断是否合理
        Node num = head;
        if(index < 0 || index >= size){
            System.out.println("这坐标不存在");
        }else{

            while(index-- > 0){
                num = num.next;
            }
            System.out.println(num.val);
        }

    }    //2. 查找 index 位置处的 信息,存在则打印其val值

    //删除单链表
   // 1.输入 index 索引值，删除该位置下的节点
    public void remove(int index){

        //如果已经没有任何有效元素了，则不进行删除
        if(size == 0){return;}
        //判断索引值是否正常
        if(index < 0 || index >= size){
            System.out.println("输入的删除索引错误，请重新输入");
        }else if(index == 0){
           head = head.next;
           size--;
        }else {
            //到这里说明，只少有两个节点
            Node p1 = head;
            Node p2 = head;
            while(index-- > 0){
                //这步p2走到了当前要删除的节点位置上
                //这步p1走到了当前要删除的节点上一个位置
                p1 = p2;
                p2 = p2.next;
            }
            p1.next = p2.next;
            size--;
        }
    }//1.输入 index 索引值，删除该位置下的节点

    //2.头删
    public void remove_First(){
        remove(0);
    }
    //3.尾删
    public void remove_Last(){
        remove(size - 1);
    }

    //4. 删除第一个值为 val 成功则返回true，否则返回 false
    public boolean remove_val(int val){

        Node num = head;
        for (int i = 0; i < size; i++) {
            if(num.val == val){
                remove(i);
                return true;
            }
            num = num.next;
        }
        return false;
    }
    //5. 删除全部值为val的节点
    public void remove_val_Pus(int val){

        while((remove_val(val)) == true);
    }

    //获得链表的长度
    public int getSize() {
        return size;
    }
}

/**
 * 单链表的每个节点-车厢类
 */
class Node{

    int val;//单链表保存的值
    Node next;//保存当前节点的下一个地址
}